/*
 * @lc app=leetcode.cn id=117 lang=swift
 *
 * [117] 填充每个节点的下一个右侧节点指针 II
 */

// @lc code=start
/**
 * Definition for a Node.
 * public class Node {
 *     public var val: Int
 *     public var left: Node?
 *     public var right: Node?
 *	   public var next: Node?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *         self.next = nil
 *     }
 * }
 */

class Solution {
    func connect(_ root: Node?) -> Node? {
        if root == nil { return root }
        var newRoot = root
        var quote: [Node] = [root!]

        while !quote.isEmpty {
            var pre: Node?
            for i in 0..<quote.count {
                let node = quote.removeFirst()

                if node.left != nil {
                    quote.append(node.left!)
                }

                if node.right != nil {
                    quote.append(node.right!)
                }

                if pre == nil {
                    pre = node
                } else {
                    pre?.next = node
                    pre = node
                }
            }
        }

        return root
    }
}
// @lc code=end

